package com.wjy.Data_Structure.tree.huffman;

import com.wjy.Data_Structure.linearlist.arraylistimpl.ListArray;
import com.wjy.Data_Structure.linearlist.common.List;
import com.wjy.Data_Structure.strategy.DefaultStrategy;
import com.wjy.Data_Structure.strategy.Strategy;
import com.wjy.Data_Structure.tree.BinTreeNode;
import com.wjy.Data_Structure.tree.BinaryTreeLinked;

public class HuffmanTreeLinked extends BinaryTreeLinked {
	public HuffmanTreeLinked(HuffmanTreeNode[] nodes) {
		this(nodes, new DefaultStrategy());
	}

	public HuffmanTreeLinked(HuffmanTreeNode[] nodes, Strategy strategy) {
		super(buildHuffmanTree(nodes), strategy);
		generateHuffmanCode((HuffmanTreeNode) super.getRoot());
	}

	/**
	 * 通过结点数组生成 Huffman 树 
	 * @param nodes 结点数组 
	 * @return  Huffman 树的根结点 
	 */
	private static BinTreeNode buildHuffmanTree(HuffmanTreeNode[] nodes) {
		int n = nodes.length;
		if (n < 2)
			return nodes[0];
		List list = new ListArray();// 根结点线性表，按weight从大到小有序
		for (int i = 0; i < n; i++)
			insertToList(list, nodes[i]);
		for (int i = 1; i < n; i++) { //选择 weight 小的两棵树合并，循环 n-1 次 
			HuffmanTreeNode min1 = (HuffmanTreeNode) list.remove(list.getSize() - 1);
			HuffmanTreeNode min2 = (HuffmanTreeNode) list.remove(list.getSize() - 1);
			HuffmanTreeNode newRoot = new HuffmanTreeNode(min1.getWeight() + min2.getWeight());
			newRoot.setLChild(min1);
			newRoot.setRChild(min2);
			insertToList(list, newRoot);
		}
		return (HuffmanTreeNode) list.get(0);
	}

	private static void insertToList(List list, HuffmanTreeNode node) {
		for (int j = 0; j < list.getSize(); j++)
			if (node.getWeight() > ((HuffmanTreeNode) list.get(j)).getWeight()) {
				list.insert(j, node);
				return;
			}
		list.insert(list.getSize(), node);

	}

	/**
	 * 递归生成Huffman编码
	 * @param root Huffman 树根结点 
	 */
	private static void generateHuffmanCode(HuffmanTreeNode root) {
		if (root == null)
			return;
		if (root.hasParent()) {
			if (root.isLChild())
				root.setCoding(root.getParent().getCoding() + "0"); //向左为 0 
			else
				root.setCoding(root.getParent().getCoding() + "1"); //向左为 0 
		}
		generateHuffmanCode(root.getLChild());
		generateHuffmanCode(root.getRChild());

	}
}
